#include <iostream>

using namespace std;

template<typename T>
class DeLinkedList {
private:
    typedef struct Node {
        T e;
        struct Node *pri, *next;

        Node(T e, struct Node *p, struct Node *n) : e(e), pri(p), next(n) {}
    } Node;
    Node *deList;
    int length{};
public:
    DeLinkedList() {
        this->deList = new Node(0, nullptr, nullptr);
    };

    DeLinkedList(T *arr, int len) {
        this->deList = new Node(0, nullptr, nullptr);
        Node *p = this->deList;
        for (int i = 0; i < len; i++) {
            Node *newNode = new Node(arr[i], p, nullptr);
            p->next = newNode;
            p = p->next;
            this->length++;
        }
    }

    void print() {
        cout << "DeLinkedList:";
        Node *ptr = this->deList;
        while (ptr->next != nullptr) {
            ptr = ptr->next;
            cout << ptr->e << " ";
        }
        cout << endl;
    }

    void insert(int pos, T value) {
        if (pos < 0)pos = 0;
        Node *p = this->deList;
        for (int i = 0; i < pos && p->next != nullptr; i++, p = p->next);
        Node *newNode = new Node(value, p, p->next);
        p->next = newNode;
        if (newNode->next != nullptr) {
            newNode->next->pri = newNode;
        }
        this->length++;
    }

    T remove(int pos) {
        if (pos < 0) pos = 0;
        if (pos >= this->length) pos = this->length - 1;
        Node *p = this->deList;
        for (int i = 0; i < pos && p->next != nullptr; i++, p = p->next);
        Node *delNode = p->next;
        p->next = delNode->next;
        if (delNode->next != nullptr) {
            delNode->next->pri = p;
        }
        T value = delNode->e;
        delete delNode;
        this->length--;
        return value;
    }

    void removeAll() {
        Node *p = this->deList;
        while (p->next != nullptr) {
            Node *delNode = p->next;
            p->next = delNode->next;
            if (delNode->next != nullptr) {
                delNode->next->pri = p;
            }
            delete delNode;
            this->length--;
        }
    }

    void push_front(int value) {
        Node *newNode = new Node(value, this->deList, this->deList->next);
        this->deList->next = newNode;
        if (newNode->next != nullptr) {
            newNode->next->pri = newNode;
        }
        this->length++;
    }

    T pop_front() {
        if (this->length != 0) {
            Node *delNode = this->deList->next;
            this->deList->next = delNode->next;
            if (delNode->next != nullptr) {
                delNode->next->pri = this->deList;
            }
            T value = delNode->e;
            delete delNode;
            this->length--;
            return value;
        }
    }

    bool isEmpty() {
        return this->length == 0;
    }

    bool size() {
        return this->length;
    }

};

int main() {

    return 0;
}
